#include <iostream>
#include <cstdlib>
using namespace std;

typedef struct lnode
{
    int data;
    struct lnode *next;
} lnode, *linklist;
/* 
删除带头结点的链表中值在min和max之间的结点
 */
// 尾插法建立单链表
int a[] = {1, 2, 3, 4, 5, 6, 7};
void makelist(linklist &l)
{
    lnode *r, *s;
    l = (lnode *)malloc(sizeof(lnode));
    l->next = nullptr;
    r = l;
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        s = (lnode *)malloc(sizeof(lnode));
        s->data = a[i];
        s->next = nullptr;
        r->next = s;
        r = s;
    }
    r = nullptr;
}

// print list
void printlist(linklist l)
{
    lnode *p = l->next;
    while (p)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}
void delmintomax(linklist &l, int min, int max)
{
    lnode *p, *q, *r;
    q = l;
    p = l->next;

    while (p && p->data <= min)
    {
        q = p;
        p = p->next;
    }
    while (p && p->data < max)
    {
        // r指向删除的位置
        r = p;
        // 删除位置的前驱指向删除位置的后继
        q->next = r->next;
        p = p->next;
        // 释放内存
        free(r);
    }
}
// 扩展直接作为无序表删除
//删除在min和max之间的结点
void RangeDelete(linklist &L, int mins, int maxs)
{
    lnode *pre = L, *p = L->next;
    while (p != NULL)
    {
        if (p->data > mins && p->data < maxs) //找到被删除的结点
        {
            pre->next = p->next;
            free(p);
            p = pre->next;
        }
        else
        {
            //不是的话继续寻找，两者都往前移
            pre = p;
            p = p->next;
        }
    } //end while
}
int main(int argc, char const *argv[])
{
    linklist l;
    makelist(l);
    printlist(l);
    delmintomax(l, 2, 5);
    printlist(l);
    return 0;
}
